/**
 * Semi-automatically generated files used to measure predicate coverage.
 * Details can be found at http://mir.cs.illinois.edu/coverage
 */
package FibHeap;

public class FibHeap {
    private Node min;

    private int n;

    public FibHeap() {
    }

    @Override
    public String toString() {
        if (min == null) {
            //executedPredicate(0, null, null);
            return "null";
        } else {
            //executedPredicate(1, null, null);
        }

        return min.toString();
    }

    private void cascadingCut(Node y) {
        Node z = y.parent;
        if (z != null) {
            //executedPredicate(2, z, null);
            if (!y.mark) {
                //executedPredicate(4, y, null);
                y.mark = true;
            } else {
                //executedPredicate(5, y, null);
                cut(y, z);
                cascadingCut(z);
            }
        } else {
            //executedPredicate(3, y, null);
        }
    }

    private void consolidate() {
        int D = n + 1;
        Node A[] = new Node[D];
        for (int i = 0; i < D; i++) {
            //executedPredicate(6, A[i], null);
            A[i] = null;
        }
        //executedPredicate(7, null, null);

        int k = 0;
        Node x = min;
        if (x != null) {
            //executedPredicate(8, x, null);
            k++;
            for (x = x.right; x != min; x = x.right) {
                //executedPredicate(10, x, null);
                k++;
            }
            //executedPredicate(11, x, null);
        } else {
            //executedPredicate(9, min, null);
        }

        while (k > 0) {
            //executedPredicate(12, min, null);
            int d = x.degree;
            Node rightNode = x.right;
            while (A[d] != null) {
                //executedPredicate(14, A[d], null);
                Node y = A[d];
                if (x.cost > y.cost) {
                    //executedPredicate(16, x, y);
                    Node temp = y;
                    y = x;
                    x = temp;
                } else {
                    //executedPredicate(17, x, y);
                }

                link(y, x);
                A[d] = null;
                d++;
            }
            //executedPredicate(15, x, null);
            A[d] = x;
            x = rightNode;
            k--;
        }
        //executedPredicate(13, min, null);
        min = null;
        for (int i = 0; i < D; i++) {
            //executedPredicate(18, A[i], null);
            if (A[i] != null) {
                //executedPredicate(20, A[i], null);
                if (min != null) {
                    //executedPredicate(22, A[i], null);
                    A[i].left.right = A[i].right;
                    A[i].right.left = A[i].left;
                    A[i].left = min;
                    A[i].right = min.right;
                    min.right = A[i];
                    A[i].right.left = A[i];
                    if (A[i].cost < min.cost) {
                        //executedPredicate(24, A[i], min);
                        min = A[i];
                    } else {
                        //executedPredicate(25, A[i], min);
                    }
                } else {
                    //executedPredicate(23, A[i], null);
                    min = A[i];
                }
            } else {
                //executedPredicate(21, min, null);
            }
        }
        //executedPredicate(19, min, null);
    }

    private void cut(Node x, Node y) {
        x.left.right = x.right;
        x.right.left = x.left;
        y.degree--;
        if (y.child == x) {
            //executedPredicate(26, x, y);
            y.child = x.right;
        } else {
            //executedPredicate(27, x, y);
        }

        if (y.degree == 0) {
            //executedPredicate(28, y, x);
            y.child = null;
        } else {
            //executedPredicate(29, x, y);
        }

        x.left = min;
        x.right = min.right;
        min.right = x;
        x.right.left = x;
        x.parent = null;
        x.mark = false;
    }

    public void decreaseKey(Node x, int c) {
        if (c > x.cost) {
            //executedPredicate(30, x, null);
            System.err.println("Error: new key is greater than current key.");
            return;
        } else {
            //executedPredicate(31, x, null);
        }

        x.cost = c;
        Node y = x.parent;
        if ((y != null) && (x.cost < y.cost)) {
            //executedPredicate(32, x, y);
            cut(x, y);
            cascadingCut(y);
        } else {
            //executedPredicate(33, x, null);
        }

        if (x.cost < min.cost) {
            //executedPredicate(34, x, min);
            min = x;
        } else {
            //executedPredicate(35, x, min);
        }

    }

    public void delete(Node node) {
        decreaseKey(node, Integer.MIN_VALUE);
        removeMin();
    }

    public boolean empty() {
        return min == null;
    }

    public void insert(int c) {
        Node n = new Node(c);
        insert(n);
    }

    public Node insert(Node toInsert) {
        if (min != null) {
            //executedPredicate(36, min, null);
            toInsert.left = min;
            toInsert.right = min.right;
            min.right = toInsert;
            toInsert.right.left = toInsert;
            if (toInsert.cost < min.cost) {
                //executedPredicate(38, min, null);
                min = toInsert;
            } else {
                //executedPredicate(39, min, null);
            }
        } else {
            //executedPredicate(37, min, null);
            min = toInsert;
        }

        n++;
        return toInsert;
    }

    private void link(Node node1, Node node2) {
        node1.left.right = node1.right;
        node1.right.left = node1.left;
        node1.parent = node2;
        if (node2.child == null) {
            //executedPredicate(40, node1, node2);
            node2.child = node1;
            node1.right = node1;
            node1.left = node1;
        } else {
            //executedPredicate(41, node1, node2);
            node1.left = node2.child;
            node1.right = node2.child.right;
            node2.child.right = node1;
            node1.right.left = node1;
        }

        node2.degree++;
        node1.mark = false;
    }

    public Node min() {
        return min;
    }

    public Node removeMin() {
        Node z = min;
        if (z != null) {
            //executedPredicate(42, z, null);
            int i = z.degree;
            Node x = z.child;
            while (i > 0) {
                //executedPredicate(44, x, z);
                Node nextChild = x.right;
                x.left.right = x.right;
                x.right.left = x.left;
                x.left = min;
                x.right = min.right;
                min.right = x;
                x.right.left = x;
                x.parent = null;
                x = nextChild;
                i--;
            }
            //executedPredicate(45, x, z);
            z.left.right = z.right;
            z.right.left = z.left;
            if (z == z.right) {
                //executedPredicate(46, x, z);
                min = null;
            } else {
                //executedPredicate(47, x, z);
                min = z.right;
                consolidate();
            }

            n--;
        } else {
            //executedPredicate(43, z, null);
        }

        return z;
    }

    public int size() {
        return n;
    }

    public FibHeap union(FibHeap heap1, FibHeap heap2) {
        FibHeap heap = new FibHeap();
        if ((heap1 != null) && (heap2 != null)) {
            //executedPredicate(48, heap1.min, heap2.min);
            heap.min = heap1.min;
            if (heap.min != null) {
                //executedPredicate(50, heap1.min, heap2.min);
                if (heap2.min != null) {
                    //executedPredicate(52, heap1.min, heap2.min);
                    heap.min.right.left = heap2.min.left;
                    heap2.min.left.right = heap.min.right;
                    heap.min.right = heap2.min;
                    heap2.min.left = heap.min;
                    if (heap2.min.cost < heap1.min.cost) {
                        //executedPredicate(54, heap1.min, heap2.min);
                        heap.min = heap2.min;
                    } else {
                        //executedPredicate(55, heap1.min, heap2.min);
                    }
                } else {
                    //executedPredicate(53, heap1.min, heap2.min);
                }
            } else {
                //executedPredicate(51, heap1.min, heap2.min);
                heap.min = heap2.min;
            }

            heap.n = heap1.n + heap2.n;
        } else {
            //executedPredicate(49, heap1.min, heap2.min);
        }

        return heap;
    }

//    public static void main(String Argv[]) {
//        FibHeap h = new FibHeap();
//        h.insert(3);
//        System.out.println(h.min().cost);
//        h.insert(2);
//        System.out.println(h.min().cost);
//        h.insert(4);
//        System.out.println(h.min().cost);
//        h.insert(1);
//        System.out.println(h.min().cost);
//        h.removeMin();
//        System.out.println(h.min().cost);
//        h.removeMin();
//        System.out.println(h.min().cost);
//        h.removeMin();
//        System.out.println(h.min().cost);
//        h.removeMin();
//        h.removeMin();
//        h.removeMin();
//    }

 //   private static int NUM_OF_PREDICATES = 14;

//    public static int numOfPredicates() {
//        return NUM_OF_PREDICATES;
//    }

//    public void //executedPredicate(int branch_id, Node n, Node m) {
//        int res = 0;
//
//        if (n != null) {
//            res |= 1 << 0;
//            res |= (n.child == null) ? 0 : 1 << 1;
//            res |= (n.parent == null) ? 0 : 1 << 2;
//            res |= (n.right == null) ? 0 : 1 << 3;
//            res |= (n.left == null) ? 0 : 1 << 4;
//            res |= (n.degree == 0) ? 0 : 1 << 5;
//        }
//        if (m != null) {
//            res |= 1 << 6;
//            res |= (m.child == null) ? 0 : 1 << 7;
//            res |= (m.parent == null) ? 0 : 1 << 8;
//            res |= (m.right == null) ? 0 : 1 << 9;
//            res |= (m.left == null) ? 0 : 1 << 10;
//            res |= (m.degree == 0) ? 0 : 1 << 11;
//        }
//        if (n != null && m != null) {
//            res |= (n.child == m) ? 0 : 1 << 12;
//            res |= (m.child == n) ? 0 : 1 << 13;
//        }
//        System.out.println("branchId=" + branch_id + "; covered predicate combination=" + res);
//    }

}